package com.algorithm.sort;

public class BinaryMergeSort {

    public static void main(String[] args) {
        int[] array = {11, 8, 3, 9, 7, 1, 2, 5};
        mergeSort(array, 0, array.length - 1);

        for (int n : array) {
            System.out.println(n);
        }
    }

    /**
     * @Description:
     * @Param: [array, from, to]
     * @return: void
     * @Author: kukuxiahuni
     * @Date: 2020/1/5
     */
    public final static void mergeSort(int[] array, int from, int to) {

        if (array == null || array.length <= 1) {
            return;
        }

        if (from >= to) {
            return;
        }

        int mid = (from + to) / 2;
        //1. 左半区排序
        mergeSort(array, from, mid);
        //2. 右半区排序
        mergeSort(array, mid + 1, to);

        merge2(array, from, mid, to);
    }


    /**
     * @Description: 合并两个半区的数组
     * @Param: [array, from, mid, to]
     * @return: void
     * @Author: kukuxiahuni
     * @Date: 2020/1/5
     */
    public final static void merge(int[] array, int from, int mid, int to) {

        if (from > mid || mid > to) {
            return;
        }

        int i = from;
        int j = mid + 1;

        int[] tmp = new int[to - from + 1];
        int index = 0;
        while (i <= mid && j <= to) {

            if (array[i] < array[j]) {
                tmp[index++] = array[i++];
            } else {
                tmp[index++] = array[j++];
            }
        }

        //如果存在没有完成排序的数据，直接拷贝
        int start = i, end = mid;
        if (j <= to) {
            start = j;
            end = to;
        }

        while (start <= end) {
            tmp[index++] = array[start++];
        }

        //将tmp数组中的数据拷贝到array的相应位置
        for (int k = 0; k < tmp.length; ++k) {
            array[from + k] = tmp[k];
        }

    }

    /**
     * 功能描述: 数组合并
     * from, mid
     * mid + 1, to
     * 将数组划分为排序的两个部分，故需要将这两个部分进行归并
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/6 10:14 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/6 10:14 上午
     **/
    private final static void merge2(int[] array, int from, int mid, int to) {

        /**
         * 额外数组
         */
        int[] tmp = new int[to - from + 1];

        int i = from, j = mid + 1;

        int index = 0;
        while (i <= mid && j <= to) {
            if (array[i] < array[j]) {
                tmp[index++] = array[i++];
            } else {
                tmp[index++] = array[j++];
            }
        }


        int k = i, end = mid;
        if (j <= to) {
            k = j;
            end = to;
        }

        for (; k <= end; ++k) {
            tmp[index++] = array[k];
        }

        //将排序数组拷贝到原数组中

        for (int l = 0; l < tmp.length; ++l) {
            array[from + l] = tmp[l];
        }

    }

}
